package fun.coding.leetcode;

import java.util.HashMap;
import java.util.Map;

public class UniquePaths {

	public static void main(String[] args) {
		UniquePaths up = new UniquePaths();
		System.out.println(up.uniquePaths(2, 2));
		System.out.println(up.uniquePaths(4, 4));
		System.out.println(up.uniquePaths(36, 7));
	}
	
	// Using math won't work... since factorial grows too fast denominator
	public int uniqueMath(int m, int n) {
		if (!(m >= 1 && n >= 1)) return 0;
		
		if (m == 1 || n == 1) return 1;
	
		m--;
		n--;
		n = m + n;
		
		int numerator = 1; // 分子
		for (int i = 0; i < m; i++) {
			numerator *= (n - i);
		}
		
		int denominator = 1; // 分母
		
		// This is factoria, number grows very quickly
		for (int i = 1; i <= m; i++) {
			denominator *= i;
		}
		return numerator / denominator;
	}
	
	// This is exponential, so it will time out for sure. 
	public int unqiuePathTimeout(int m, int n) {
		if (m == 1 || n == 1) return 1;
		
		return unqiuePathTimeout(m-1, n) + unqiuePathTimeout(m,n-1);
	}
	
	// With lookup table top down
	public int uniquePathsHelper(int m, int n, Map<String, Integer> lookup) {
		String key = m + "," + n;
		if (lookup.containsKey(key)) return lookup.get(key);
		
		if (m == 1 || n == 1) return 1;
		
		int res = uniquePathsHelper(m-1, n, lookup) + uniquePathsHelper(m, n-1, lookup);
		lookup.put(key, res);
		return res;
	}
	
	public int uniquePaths(int m, int n) {
		if (!(m >= 1 && n >= 1)) return 0;
		Map<String, Integer> lookup = new HashMap<String, Integer>();
		return uniquePathsHelper(m, n, lookup);
	}
	
	// DP with 2-dimensional array
    public int uniquePathsDp(int m, int n) {
    	if (!(m >= 1 && n >= 1)) return 0;
    	
    	int[][] lookup = new int[m][n];
    	
    	for (int i = 0; i < m; i++) {
    		lookup[i][0] = 1;
    	}
    	for (int i = 0; i < n; i++) {
    		lookup[0][i] = 1;
    	}
    	
    	for (int i = 1; i < m; i++) {
    		for (int j = 1; j < n; j++) {
    			lookup[i][j] = lookup[i-1][j] + lookup[i][j-1];
    		}
    	}
    	return lookup[m-1][n-1];
    }
    
    // save space by using 滚动数组
    public int uniquePathsDpOptimized(int m, int n) {
    	if (!(m >= 1 && n >= 1)) return 0;
    	
    	int[] max = new int[n];
    	
    	for (int i = 0; i < n; i++) {
    		max[i] = 1;
    	}
    	
    	for (int i = 1; i < m; i++) {
    		for (int j = 1; j < n; j++) {
    			max[j] = max[j] + max[j-1]; 
    		}
    	}
    	return max[n-1];
    }

}
